import java.util.HashMap;

/**
* @description: 873. 最长的斐波那契子序列的长度
* @author hewei
* @date 2022/9/13 14:54
* @version 1.0
*/

public class LenLongestFibSubseq {

    public static void main(String[] args) {
        int[] nums = {2,4,7,8,9,10,14,15,18,23,32,50};
        System.out.println(new LenLongestFibSubseq().lenLongestFibSubseq(nums));
    }

    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        HashMap<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; i++) {
            index.put(arr[i], i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (index.containsKey(arr[i] - arr[j]) && index.get(arr[i] - arr[j]) < j) {
                    dp[j][i] = Math.max(3, dp[index.get(arr[i] - arr[j])][j] + 1);
                }
                ans = Math.max(ans, dp[j][i]);
            }
        }
        return ans;
    }
}